home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / N_TREE.C < prev    next >
C/C++ Source or Header  |  1992-09-28  |  12KB  |  340 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12.  
  13. #include <cool/N_Tree.h>
  14.  
  15. // CoolN_Tree -- Simple constructor that sets the root to the node provided
  16. // Input:    Pointer to node object or NULL.
  17. // Output:   CoolN_Tree object created with root initialized
  18.  
  19. template <class Node> 
  20. CoolN_Tree<Node>::CoolN_Tree(Node* n) {
  21.   this->root = n;                // Point root to node
  22.   this->t_mode = INORDER;            // Default traversal mode
  23.   if (n)
  24.     this->number_nodes = 1;            // Update node count
  25.   else
  26.     this->number_nodes = 0;
  27. }
  28.  
  29. // CoolN_Tree -- Simple constructor that sets the root to the node provided
  30. // Input:    Reference to node object
  31. // Output:   CoolN_Tree object created with root initialized
  32.  
  33. template <class Node> 
  34. CoolN_Tree<Node>::CoolN_Tree(Node& n) {
  35.   this->root = &n;                // Point root to node
  36.   this->t_mode = INORDER;            // Default traversal mode
  37.   this->number_nodes = 1;            // Update node count
  38. }
  39.  
  40.  
  41. // CoolN_Tree -- Copy constructor makes deep copy of all nodes
  42. // Input:    Reference to CoolN_Tree object
  43. // Output:   CoolN_Tree object duplicated
  44.  
  45. template <class Node> 
  46. CoolN_Tree<Node>::CoolN_Tree(const CoolN_Tree<Node>& nt) 
  47. {
  48.   this->root = copy_nodes(nt.root);        // Deep copy of all nodes
  49.   this->t_mode = nt.t_mode;            // Copy traversal mode
  50.   this->number_nodes = nt.number_nodes;        // Copy node count
  51.   this->state = nt.state;            // Copy state or curpos
  52. }
  53.  
  54.  
  55. // ~CoolN_Tree -- destructor (not inline because it's virtual)
  56. // Input:    none
  57. // Output:   none
  58.  
  59. template <class Node>
  60. CoolN_Tree<Node>::~CoolN_Tree() {
  61.   delete this->root;                // Delete all nodes
  62. }
  63.  
  64. // clear -- removes root and all subtrees
  65. // input -- none
  66. // output -- none
  67.  
  68. template <class Node> 
  69. void CoolN_Tree<Node>::clear () {
  70.   delete this->root;                // Delete all nodes
  71.   this->root = NULL;
  72.   this->number_nodes = 0;
  73.   this->reset();
  74. }
  75.  
  76.  
  77.  
  78. // prev -- Move position to previous node in tree. If no more nodes
  79. //         return FALSE 
  80. // Input:  None
  81. // Output: TRUE/FALSE
  82.  
  83. template <class Node> 
  84. Boolean CoolN_Tree<Node>::prev() {
  85.   Traversal_Type reverse_mode;
  86.   switch (this->t_mode) {
  87.   case INORDER:
  88.     reverse_mode = INORDER_REVERSE;
  89.     break;
  90.   case INORDER_REVERSE:
  91.     reverse_mode = INORDER;
  92.     break;
  93.   case PREORDER:
  94.     reverse_mode = PREORDER_REVERSE;
  95.     break;
  96.   case PREORDER_REVERSE:
  97.     reverse_mode = PREORDER;
  98.     break;
  99.   case POSTORDER:
  100.     reverse_mode = POSTORDER_REVERSE;
  101.     break;
  102.   case POSTORDER_REVERSE:
  103.     reverse_mode = POSTORDER;
  104.     break;
  105.   }
  106.   return this->next_internal (reverse_mode);
  107. }
  108.   
  109. // Get the next node in the tree based on the Traversal Type.  This
  110. // maintains a stack of parents in the tree for current position and
  111. // knows how to move forward and backward for preorder, inorder, or
  112. // postorder traversals. Changes here are most likely necessary in
  113. // Base_BT.C next_internal also.
  114.  
  115. template <class Node>
  116. Boolean CoolN_Tree<Node>::next_internal (Traversal_Type ttype) {
  117.   Node* node;
  118.   Node* ptr1;
  119.   Node* last_node = NULL;
  120.   CoolNT_Stack_Entry stack_entry;
  121.   int index;
  122.   Boolean forward = TRUE;
  123.  
  124.   switch (ttype) {
  125.   case INORDER_REVERSE:
  126.   case PREORDER_REVERSE:            // Are we going backward?
  127.   case POSTORDER_REVERSE:
  128.     forward = FALSE;
  129.     break;
  130.   }
  131.     
  132.   if (state.stack.is_empty()) {            // If stack is empty
  133.     node = this->root;                //  start with the root
  134.     if (forward)                //  init starting subtree
  135.       index = -1;                //    start at first subtree
  136.     else                    //    or
  137.       index = node->num_subtrees();        //    start at last subtree
  138.     state.stack.push (CoolNT_Stack_Entry ((long)node,index));
  139.     state.forward = forward;
  140.     
  141.   }
  142.   else {                    // Stack has some entries, so
  143.     stack_entry = state.stack.top();        //  get top entry from stack
  144.     node = (Node*)stack_entry.get_first();    //  load up node
  145.     index = (int)stack_entry.get_second();    //  and subtree index
  146.     last_node = node;                //  remember current position
  147.  
  148.     if (state.forward != forward) {        // Need to modify index
  149.       if (forward)                //  if we've changed direction.
  150.     index--;
  151.       else
  152.     index++;
  153.     }
  154.     state.forward = forward;            // Update direction.
  155.   }
  156.  
  157.   if (forward) {                // Going left to right
  158.     while (TRUE) {                // loop until next node found
  159.       if (++index < node->num_subtrees()) {    // incremented index in range?
  160.     if (node != last_node &&        // If we moved to new node &&
  161.         ((ttype == INORDER  && index == 1)  // Inorder after ltree or
  162.          ||(ttype == PREORDER && index == 0)// Preorder before ltree
  163.          ))
  164.       return TRUE;                // then this is next node
  165.  
  166.     state.stack.top().set_second(index);    // update stack with new index
  167.     ptr1 = node->sub_trees[index];        // get node's next subtree
  168.     if (ptr1) {                // When subtree exists
  169.       node = ptr1;                //   point node at subtree
  170.       index = -1;                //   init index for new node
  171.       state.stack.push (CoolNT_Stack_Entry ((long)node, index)); 
  172.     }
  173.       }
  174.       else {                    // No more subtrees for node
  175.     if (node != last_node &&        // If a new node
  176.         ttype == POSTORDER) {        //   and Postorder mode, 
  177.       return TRUE;                //   then this is next node
  178.     }
  179.     state.stack.pop();// pop this node from stack
  180.     if (state.stack.is_empty())            // Stack empty?
  181.       return FALSE;                //   indicate we're at the end
  182.         else {                    // Stack not empty, so
  183.       stack_entry = state.stack.top();    //  update stack_entry object
  184.       node = (Node*)stack_entry.get_first(); //  load up node
  185.       index = stack_entry.get_second();    //  and subtree index
  186.     }
  187.       }
  188.     }
  189.   }
  190.  
  191. // This is essesentially the same code as above, but going right to
  192. // left, giving reverse order capability
  193.   else {                                        // Going right to left
  194.     while (TRUE) {                // loop until next node found
  195.       if (--index > -1) {            // decremented index in range?
  196.     if (node != last_node &&        // If we moved to new node &&
  197.         ((ttype == INORDER_REVERSE &&    //  or Inorder_reverse node
  198.           index == 0)             //  is ready to do left subtree
  199.           || (ttype == POSTORDER_REVERSE &&    //  or Postorder_reverse is
  200.           index == (node->num_subtrees()-1))  // starting it's subtrees
  201.          ))
  202.       return TRUE;                // then this is next node
  203.     state.stack.top().set_second(index);    // update stack with new index
  204.     ptr1 = node->sub_trees[index];            // get node's next subtree
  205.     if (ptr1) {                // When subtree exists
  206.       node = ptr1;                //   point node at subtree
  207.       index = node->num_subtrees();        //   init index for new node
  208.       state.stack.push (CoolNT_Stack_Entry ((long)node, index)); 
  209.     }
  210.       }
  211.       else {                    // No more subtrees for node
  212.     if (node != last_node &&        // If a new node
  213.         ttype == PREORDER_REVERSE)             //   and Preorder_reverse
  214.       return TRUE;                //   this is next node
  215.  
  216.     state.stack.pop();            // pop this node from stack
  217.     if (state.stack.is_empty())        // Stack empty?
  218.       return FALSE;                //   indicate we're at the end
  219.         else {                    // Stack not empty, so
  220.       stack_entry = state.stack.top();    //  update stack_entry object
  221.       node = (Node*)stack_entry.get_first(); //  load up node
  222.       index = (int)stack_entry.get_second();    //  and subtree index
  223.     }
  224.       }
  225.     }
  226.   }
  227. }
  228.  
  229.  
  230. #if 0  //## BC++ 3.1 has problems with nested typedefs
  231.  
  232. // value -- Return value of node at current position
  233. // Input: None
  234. // Output: Reference to value of node at current position
  235.  
  236. template <class Node> 
  237. Node::ItemType& CoolN_Tree<Node>::value () { 
  238. #if ERROR_CHECKING 
  239.   if (this->state.stack.is_empty() )        // If no position established
  240.     this->value_error ();            // Raise exception
  241. #endif
  242.   CoolNT_Stack_Entry stack_entry = this->state.stack.top();
  243.   return (((Node*)stack_entry.get_first())->get());
  244. }
  245.  
  246. // find -- Search the tree for a particular value. If found, update the current
  247. //         position marker.
  248. // Input:  Reference of value to search for
  249. // Output: TRUE/FALSE
  250.  
  251. template <class Node> 
  252. Boolean CoolN_Tree<Node>::find (const Node::ItemType& value) {
  253.   for (this->reset (); this->next (); )     // For each node in tree
  254.     if (this->value() == value)            // If node found in tree
  255.       return TRUE;                // Inidicate success
  256.   return FALSE;                    // Inidicate failure
  257. }
  258.  
  259.  
  260. // preorder -- Perform a preorder traversal of tree by setting traversal mode,
  261. //             making node pointer cache, and applying function to each node
  262. // Input:      Pointer to function to apply to each node
  263. // Output:     None
  264.  
  265. template <class Node> 
  266. void CoolN_Tree<Node>::preorder (/*Apply_Function##*/Boolean (*fn)(const Node::ItemType&)) {
  267.  
  268.   if (this->t_mode != PREORDER)         // If incorrect traversal mode
  269.     this->t_mode = PREORDER;            // Set preorder mode
  270.  
  271.   for (this->reset() ; this->next (); )        // For each preorder node
  272.     (*fn)(this->value());            // Apply function
  273. }
  274.  
  275.  
  276. // inorder -- Perform an inorder traversal of tree by setting traversal mode,
  277. //            making node pointer cache, and applying function to each node
  278. // Input:     Pointer to function to apply to each node
  279. // Output:    None
  280.  
  281. template <class Node> 
  282. void CoolN_Tree<Node>::inorder (/*Apply_Function##*/Boolean (*fn)(const Node::ItemType&)) {
  283.   if (this->t_mode != INORDER)          // If incorrect traversal mode
  284.     this->t_mode = INORDER;            // Set inorder mode
  285.  
  286.   for (this->reset() ; this->next (); )        // For each preorder node
  287.     (*fn)(this->value());            // Apply function
  288. }
  289.  
  290.  
  291. // postorder -- Perform a postorder traversal of tree by setting traversal mode,
  292. //              making node pointer cache, and applying function to each node
  293. // Input:       Pointer to function to apply to each node
  294. // Output:      None
  295.  
  296. template <class Node> 
  297. void CoolN_Tree<Node>::postorder (/*Apply_Function##*/Boolean (*fn)(const Node::ItemType&)) {
  298.   if (this->t_mode != POSTORDER)         // If incorrect traversal mode
  299.     this->t_mode = POSTORDER;            // Set postorder mode
  300.  
  301.   for (this->reset() ; this->next (); )        // For each preorder node
  302.     (*fn)(this->value());            // Apply function
  303. }
  304. #endif
  305.  
  306. // current_position -- Get/Set iterator object for Tree
  307. // Input:              None
  308. // Output:             NT_State object of the Tree
  309.  
  310. template <class Node>
  311. CoolNT_State& CoolN_Tree<Node>::current_position () {
  312.   return this->state;
  313. }
  314.  
  315.  
  316. // do_count -- Perform an preorder traversal of N-ary tree to count nodes
  317. // Input:       Pointer to sub-tree node
  318. // Output:       None
  319.  
  320. template <class Node>
  321. void CoolN_Tree<Node>::do_count (Node* t) {
  322.   if (t != NULL) {                // If there is a subtree
  323.     this->number_nodes++;            // Increment node count
  324.     for (int i = 0; i < Node::max_children(); i++)        // For each pointer in vector
  325.       this->do_count (t->sub_trees[i]);        // Traverse each subtree
  326.   }
  327. }
  328.  
  329. // value_error -- Raise exception for CoolN_Tree::value()
  330. // Input:         None
  331. // Output:        None
  332.  
  333. template <class Node> 
  334. void CoolN_Tree<Node>::value_error () {
  335.   //RAISE Error, SYM(CoolN_Tree), SYM(Invalid_Cpos),
  336.   printf ("CoolN_Tree<%s,%s,%d>::value(): Invalid current position.\n",
  337.           "Node::ItemType", "Node", Node::max_children());
  338.   abort ();
  339. }
  340.